package com.yanqu.road.server.manager.unionwar;

import com.yanqu.road.utils.RandomHelper;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

/**
 * 二维数组占位模拟随机匹配阵容
 */
public class MatchEnemySimulate {

    private static RandomHelper randomHelper = new RandomHelper();

    /**
     * v2.6 分区间随机匹配
     * 整体划分成若干区间，子区间按v2.5穷尽方式获得的结果在偏移回整体。区间穷尽方式可以存在区间自己匹配，这是与区间内元素不能自己匹配自己的唯一差别
     * @param allRound
     * @param joinSize 必须是1至20其中一个数的偶数倍且大于allRound
     * @return
     */
    public static int[][] randomMatchInNSessionV26(int allRound, int joinSize){
        //计算分n个区间[4,m^0.4)
        int section = (int)(Math.floor(Math.pow(joinSize, 0.4)));
        //总数能被区间整除且区间内的个数必须偶数
        while ((joinSize % section != 0 || (joinSize / section) % 2 != 0) && section > 2){
            section--;
        }
        if((joinSize / section) % 2 != 0){
            section = 2;
        }
        while(allRound % section != 0){
            allRound++;
        }
        System.out.println("joinSize:"+ joinSize + ", section:" + section);
        int roundSection = section;
        int roundPerSection = allRound / section;
        int sizePerSection = joinSize / section;
        int[][] zone = new int[roundSection][section];  //先按划分的区间，匹配区间
        int[][] data = new int[allRound][joinSize];  //整体匹配数据，即结构
        for (int i = 0; i < 100; i++) { //最多尝试100次
            randomSession(zone, false);  //区间匹配，区间可匹配自己（仅有一次）
            if (isAllFill(zone)) {
                break;
            } else {
                zone = new int[roundSection][section];
            }
        }
        //print(zone);
        if(isAllFill(zone)){

        }else {
            return data;  //失败
        }
        //print(zone);//区间匹配完成
        for(int i = 0; i < roundSection; i++){ //session
            for(int j = 0; j < section; j++){  //union
                int[][] result = new int[roundPerSection][sizePerSection];
                for (int t = 0; t < 100; t++) { //最多尝试100次
                    randomSession(result, true);//此处必须为true，表示区间内元素自己不可匹配自己
                    if (isAllFill(result)) {
                        break;
                    } else {
                        result = new int[roundPerSection][sizePerSection];
                    }
                }
                if(isAllFill(result)){
                    //print(result);
                    //复制匹配结果
                    for(int k = 0; k < result.length; k++){
                        for(int l = 0; l < result[0].length; l++){
                            //偏移
                            int sessionOffset = i * roundPerSection;  //场次
                            int unionOffset = j * sizePerSection;     //参与者
                            //result[k][l] = 9 即第k场l的对手是 9
                            int curSession = sessionOffset + k;
                            int curUnion = l + unionOffset;
                            int enemy = result[k][l] + (zone[i][j] - 1) * sizePerSection;
                            data[curSession][curUnion] = enemy;
                            data[curSession][enemy - 1] = curUnion + 1;
                        }
                    }
                }else {
                    return data;  //失败
                }
            }
        }
        print(data);
        return data;
    }

    /**
     * 随机交换行数据
     * @param data
     */
    public static void randomExchangeRow(int[][] data){
        List<Integer> allRow = new ArrayList<>();
        for(int row = 0; row < data.length; row++){
            allRow.add(row);
        }
        List<Integer> result = new ArrayList<>();
        while (allRow.size() > 0){
           int idx = randomHelper.next(0, allRow.size());
           result.add(allRow.get(idx));
           allRow.remove(idx);
        }
        for(int i = 0; i < result.size() - 1;i = i + 2){
            int row1 = result.get(i);
            int row2 = result.get(i + 1);
            int temp;
            for(int j = 0; j < data[0].length; j++){
                temp = data[row1][j];
                data[row1][j] = data[row2][j];
                data[row2][j] = temp;
            }
        }
    }

    //--------------------------- v2.5 Help  -----------------------
    private static void removePool(List<Integer> pool, int obj1) {
        Iterator<Integer> iterator = pool.iterator();
        while (iterator.hasNext()) {
            Integer obj = iterator.next();
            if (obj.intValue() == obj1) {
                iterator.remove();
            }
        }
    }

    public static boolean isAllFill(int[][] data){
        for(int r = 0; r < data.length; r++){
            for(int c = 0; c < data[0].length; c++){
                //0为未初始化
                if(data[r][c] == 0){
                    return false;
                }
            }
        }
        return true;
    }
    //--------------------------- v2.5 Help -----------------------

    public static void main(String[] args) {
        for(int start = 192; start < 194; start = start +2) {
            boolean support = false;
            for (int i = 0; i < 1; i++) { //尝试次数
                int[][] data = randomMatchInNSessionV26(24, start);
                if (isAllFill(data)) {
                    //print(data);
                    System.out.println("-----------------------");
                    randomExchangeRow(data);
                    //print(data);
                    support = true;
                    break;
                }
            }
            if(!support) {
                System.out.println(start + " no support");
            }
        }
//        int[][] data = new int[5][5];
//        randomSession(data,false);
//        print(data);
    }

    public static void print(int[][] data) {
        for(int c = 1; c <= data[0].length; c++){
            System.out.print(c  + "   ");//固定输出1-n,代表总个数
        }
        System.out.println(" ");
        for(int r = 0; r < data.length; r++){
            for(int c = 0; c < data[0].length; c++){
                System.out.print(data[r][c]);
                if(data[r][c] < 10){
                    System.out.print("   ");
                }else{
                    System.out.print("  ");
                }
                if(c > 9){
                    System.out.print(" ");
                }
            }
            System.out.println(" ");
        }
    }


    //---------------v2.5
    /**
     * 初始所有场次匹配
     * @param data
     * @param filterSelf  是否过滤自己
     */
    public static void randomSession(int[][] data, boolean filterSelf){
        for(int session = 0; session < data.length; session ++){
            randomPosition(data, session, 0, 1, filterSelf);
        }
    }

    /**
     * 初始每场对手
     * @param data
     * @param r
     * @param c
     * @param deep
     * @param filterSelf  是否过滤自己
     */
    public static void randomPosition(int[][] data, int r, int c, int deep, boolean filterSelf){
        deep++;
        if(deep > 2000){ //调用栈深度
            return;
        }
        if(data[r][c] > 0){ //已匹配，下一个坑
            nextFillPosition(data, r, c, deep, filterSelf);
            return;
        }
        //初始备选池，值从1开始
        List<Integer> pool = new ArrayList<>();
        for(int n = 1; n <= data[0].length; n++){
            if(n == c + 1 && filterSelf){ //过滤自己
                continue;
            }
            pool.add(n);
        }
        //过滤当前场次已选中
        for(int col = 0; col < data[0].length; col++){
            if(data[r][col] > 0){
                removePool(pool, data[r][col]);
            }
        }
        //过滤历史已配对
        for(int row = 0; row < r; row ++){
            if(data[row][c] > 0){
                removePool(pool, data[row][c]);
            }
        }
        //回退至0坑
        if(pool.size() == 0){
            for(int i = 0; i < data[0].length; i++){//重置当前行
                data[r][i] = 0;
            }
            randomPosition(data, r, 0, deep, filterSelf);
            return;
        }
        //选择
        int idx = randomHelper.next(0, pool.size());
        int val =  pool.get(idx);
        data[r][c] = val;  //本坑
        data[r][val-1] = c + 1; //配对坑
        //匹配完成，下一个坑
        nextFillPosition(data, r, c, deep, filterSelf);
    }

    private static void nextFillPosition(int[][] data, int r, int c, int deep, boolean filterSelf) {
        //当前场，下一个坑
        if (c + 1 < data[0].length) {
            randomPosition(data, r, c + 1, deep, filterSelf);
        }
    }

    //---------------v2.5
}
